package org.ww.algorithm.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GraphDemo {

    private List<String> vertexList;  //存放节点的列表
    private int[][] edges;   //存放边和边之间的关系
    private int edgesNums;   //存放边的条数
    private boolean[] isExist; //当前节点是否被访问过

    public static void main(String[] args) {
        int n=5;
        String vertex[]={"A","B","C","D","E"};
        GraphDemo graphDemo=new GraphDemo(n);
        for(String a:vertex){
            graphDemo.addVertex(a);
        }
        graphDemo.join(0,1,1);
        graphDemo.join(0,2,1);
        graphDemo.join(1,2,1);
        graphDemo.join(1,3,1);
        graphDemo.join(1,4,1);

        graphDemo.getGraph();

        graphDemo.dfs();
    }
    //n代表n个节点
    public GraphDemo(int n) {
        vertexList=new ArrayList<>(n);
        edges=new int[n][n];
        edgesNums=0;
        isExist=new boolean[n];
    }

    //查找当前节点的第一个相邻节点
    public int getFirstNeiber(int i){
        for(int j=0;j<vertexList.size();j++){
            if(edges[i][j]>0){
                return j;
            }
        }
        return -1;
    }

    //查找当前节点的下一个相邻节点
    public int getNextNeiber(int v1,int v2){
        for(int i=v2+1;i<vertexList.size();i++){
            if(edges[v1][i]>0){
                return i;
            }
        }
        return -1;
    }

    //深度优先搜索
    public void dfs(boolean[] isExist,int i){
        //打印当前遍历的节点
        System.out.print(vertexList.get(i)+"-->");
        //将当前节点置为访问过的
        isExist[i]=true;
        //获取当前节点的第一个相邻节点
        int w = getFirstNeiber(i);
        while (w!=-1){  //说明当前节点存在相邻的节点
            if(!isExist[w]){ //如果相邻节点没有被访问过
                dfs(isExist, w);
            }
            //相邻节点访问过，继续查找下一个相邻的节点
            w=getNextNeiber(i,w );
        }
    }

    //对每一个节点进行是深度优先搜索
    private void dfs(){
        for(int i=0;i<vertexList.size();i++){
            if(!isExist[i]){
                dfs(isExist,i );
            }
        }
    }

    //添加边关系   weight表示权值
    public void join(int v1,int v2,int weight){
        edges[v1][v2]=weight;
        edges[v2][v1]=weight;
        edgesNums++;   //添加边
    }

    //添加节点信息
    public void addVertex(String vertex){
        vertexList.add(vertex);
    }

    //获取图关系
    public void getGraph(){
        for(int[] i:edges){
            System.out.println(Arrays.toString(i));
        }
    }
}
